ITI 1120 Winter 2013 - Assignment 4

Available: Tuesday, March 16, 2013
Due: Friday, March 29, 22:00,

Instructions

This assignment is to be done in TEAMS OF TWO PEOPLE. The assignment should be submitted only once by a member of your team, but please ensure that the identification material contains the information for both team members. Java code is required. Zip all the files in a4_xxxxxx.zip, where xxxxxx is the student number of one of the partners, and submit it through the Blackboard Learn).

Marking Scheme (total 100 marks)

 Introduction to a game of Sudoku

The Sudoku is a game based on a 9x9 grid; the goal is to fill the grid with digits from 1 to 9 while respecting certain constraints. Some digits are already inserted 1into the grid.


In the image above, the coordinates are given by the row number (from1 to 9, starting from the top) and the column number (from 1 to 9, from left to right).

The main constraints are:

Your task consists in completing several methods in a given incomplete code for the Sudoku game. The headers of the methods are provided (with the return values temporarily empty so that the program can compile). There are also several JUnit tests that allow you to test each of your methods.

There are seven files provided:

 Question 1 (20 marks)

Complete the following method in the class MatriceLib:

  public static int[][] rotation (int[][] matrix)

This method rotates clockwise a square matrix (assume that the matrix has size bigger than 0). Note that this operation is different from the transposition of a matrix. The MatriceLibTest class contains three tests that allow you to check your solution.

Example: for the matrix
{{ 0, 1, 2},

{10, 11, 12},

{20, 21, 22}}

The rotated matrix is:
 {{20, 10, 0},

{21, 11, 1},

{22, 12, 2}}

 Question 2 (15 marks)

Complete the following method from the class SudokuLib:

  public static boolean solved(int[][] sudoku)

This method determines if a sudoku grid (that contains 9x9 digits from 0 to 9) was entirely solved. Assume that the given grid is valid:  it satisfies the constraints enumerated above. Note that the sum of the numbers from 1 to 9 is 45. The class SudokuLibTest contains two tests for verifying your solution.

 Question 3 (15 marks)

Complete the following method from the class SudokuLib:

  public static void generateConstraints(int[][] sudoku, boolean[][] constraints)

In order to allow the program to remember the positions where the initial values were in the sudoku grid, we use a matrix of Boolean values of the same size as the grid. For each cell of the sudoku grid that contains an initial value bigger than 0, the matrix of constraints will contain true in the same position. Once generated, this matrix will not be modified during the game. For example, the last row of the matrix of constraints corresponding to the sudoku grid from the above figure is {false, false, false, false, false, false, false, true, true}.

The sudoku matrix is given as entry and should not be changed, but the matrix of boolean constraints will be modified by this method. The class SudokuLibTest contains a test for verifying your solution.

Note that as soon as the matrix of constraints becomes available in your code, the initial values (in the positions marked with true) will be automatically displayed in red (before that they are in black in the starter code).

 Question 4 (20 marks)

Complete the following method from the class SudokuLib:

  public static int[][] generateSudoku(boolean[][] constraints)

To simplify the task of random creation of an initial grid that is valid and can be solved (this is a very complex problem), we use here a simpler method: we randomly choose a sudoku grid from a predefined grid (there are 4 in the library class, accessible by invoking the private method SudokuGrids). For increasing the number of possible combinations, generateSudoku could also do between 0 and 3 rotations (randomly) of the chosen grid; this brings the number pf possible configurations to 4x4 = 16!!!. generateSudoku has to invoke generateConstraints, and this will modify the matrix of constraints given as parameter. Finally, the method returns the sudoku grid that was "randomly generated". There are no specific JUnit tests for this method because it involves random values.

 Question 5 (20 marks)

Complete the following method from the class SudokuLib:

  public static boolean verifyGuess(int row, int col, int guess, int[][] sudoku, boolean[][] constraints, boolean messages)

This method has the goal to ensure that the guess tried by the player would preserve the validity of the sudoku grid. A guess is composed by a row index (between 0 and 8 for this method), a column index (between 0 and 8 for this method) and a value for the guess (a digit to place on the grid, between 0 and 9). The use interface already verifies the individual validity of each of these values, but not their ensemble. The method has to return false if the guess tries to:

  1. modify a value from the initial grid (error message: You cannot modify an initial value (in red) )
  2. insert twice the same digit in the same row (error message: Sorry, it is already present in the row!)
  3. insert twice the same digit in the same column (error message: Sorry, it is already present in the column!)
  4. insert twice the same digit in the same zone (error message: Sorry, it is already present in the 3x3 zone!)

The boolean value messages indicates if we need to display an error message. The method is invoked with the value true in the program, and with the value false in the tests because we want to keep the tests automatic, to not have to click on buttons for each test! The messages are displayed in a dialogue box as follows:

      if (messages)
        JOptionPane.showMessageDialog(null, " You cannot modify an initial value (in red)");

To help you, the code for verifying the first constraint is already provided, and you have to implement the other three (which are complex enough to deserve separate methods ...!)

Note that the program displays in blue the last digit inserted and in black the digits previously inserted. If? 0 is input as the guess, when it is not for deleting an initial value, no message needs to be displayed.

This method does not modify the sudoku grid (the updating of the grid is done in one of the two classes for which you do not have the code) and the matrix of constraints. The class SudokuLibTest contains six tests that you can use to verify your solution.

 Bonus (recursivity)


Enjoy the sudoku game!